| [c语言]二叉树 非递归算法（先中后遍历）come | 您所在的位置：网站首页 › 完全二叉树 递归 › [c语言]二叉树 非递归算法（先中后遍历）come |
[c语言]二叉树 非递归算法（先中后遍历）come
|
今天本篇文章将会讲解c语言二叉树的非递归算法并加附代码。 非递归其实就是非递归遍历，非递归运用了 栈 的思想，包括了先中后3种方式遍历，费话不多说，开整。 1.定义头文件加结构体变量代码语言：javascript复制#include #include #include typedef struct TreeNode { char data; struct TreeNode* lchild; struct TreeNode* rchild; int flag; }TreeNode; typedef struct StackNode { TreeNode* data; struct StackNode* next; }StackNode;注：这里定义的flag会在后序遍历中用到。（用来标记结点是否被访问过） 2.创建一棵树代码语言：javascript复制void creatTree(TreeNode** T,int* index,char* data) { char ch; ch = data[*index]; (*index)++; if (ch == '#') *T = NULL; else { *T = (TreeNode*)malloc(sizeof(TreeNode)); (*T)->data = ch; (*T)->flag = 0; creatTree(&((*T)->lchild), index, data); creatTree(&((*T)->rchild), index, data); } }注：此处不再详细解释，如果不懂可以参考本站另一篇文章http://t.csdn.cn/jX4cd  3.初始化栈代码语言：javascript复制StackNode* initStack()
{
StackNode* s = (StackNode*)malloc(sizeof(StackNode));
s->data = NULL;
s->next = NULL;
return s;
}注：把栈置为空（初始化） 4.头插法入栈代码语言：javascript复制void headpush(TreeNode* data, StackNode* s) { StackNode* node = (StackNode*)malloc(sizeof(StackNode)); node->data = data; node->next = s->next; s->next = node; }注：入栈（头插法），即对指针进行操作。 5.判断栈是否为空代码语言：javascript复制int is_empty(StackNode* s) { if (s->next == NULL) return 1; else return 0; }6.出栈操作代码语言：javascript复制StackNode* pop(StackNode* s) { if (is_empty(s)) return NULL; else { StackNode* node = s->next; s->next = node->next; return node; } }注：出栈之前要先判断一下是否为空栈，不为空再进行出栈，因为出的是栈顶元素直接指针断开即可。 下面重点来了：非递归先序、中序，后序遍历。 7.先序遍历代码语言：javascript复制void preOrder(TreeNode* t) { TreeNode* node = t; StackNode* s = initStack(); while (node || !is_empty(s)) { if (node) //判断node是否为空 { printf("%c ", node->data); headpush(node, s); node = node->lchild; } else { node = pop(s)->data; node = node->rchild; } } }注：先序遍历：根左右，先打印根 ，然后入栈，找根的左孩子，然后判断左孩子是否为空，两种情况：1为空：那就会进入else语句，出栈，找它的右孩子，再进行判断。2不为空：就先打印，再入栈，再找它的左孩子，从而再进行判断。一直往复循环，直到不满足while条件时遍历结束。 8.中序遍历代码语言：javascript复制void inOrder(TreeNode* t) { TreeNode* node = t; StackNode* s = initStack(); while (node || !is_empty(s)) { if (node) { headpush(node, s); node = node->lchild; } else { node = pop(s)->data; printf("%c ", node->data); node = node->rchild; } } }注：与先序遍历一样，就是打印语句转移到了else语句，基本思路一致。 9.后序遍历代码语言：javascript复制StackNode* getTop(StackNode* s) { if (is_empty(s)) return NULL; else { StackNode* node = s->next; return node; } } //先获取栈顶元素，因为不需要出栈，所以重新写了一个函数 void postOrder(TreeNode* t) { TreeNode* node = t; StackNode* s = initStack(); while (node || !is_empty(s)) { if (node) { headpush(node, s); node = node->lchild; } else { TreeNode* top = getTop(s)->data; if (top->rchild && top->rchild->flag == 0) { top = top->rchild; headpush(top, s); node = top->lchild; } else { top = pop(s)->data; printf("%c ", top->data); top->flag = 1; } } } }注：所有遍历操作，基本上整体大的框架没有改变。 如果没有flag作为标记，会陷入死循环。 10.主函数调用代码语言：javascript复制int main() { int index = 0; TreeNode* t; char data[100]; gets_s(data); creatTree(&t, &index, data); preOrder(t); printf("\n"); inOrder(t); printf("\n"); postOrder(t); return 0; }11.运行结果：代码语言：javascript复制ab##c## a b c //先序 b a c //中序 b c a //后序 D:\VS\二叉树非递归\x64\Debug\二叉树非递归.exe (进程 12216)已退出，代码为 0。 按任意键关闭此窗口. . . |
【本文地址】
公司简介
联系我们
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |